Floyd-Warshall Algorithm

The Floyd-Warshall Algorithm is a dynamic programming method used to find the shortest paths between all pairs of nodes in a weighted graph. This algorithm can handle both directed and undirected graphs and works with graphs that have negative weight edges, though it cannot handle graphs with negative weight cycles.

Properties

• Algorithm Type: Dynamic Programming
• Graph Type: Weighted graph (both directed and undirected)
• Edge Weights: Positive or negative (but no negative weight cycles)
• Complexity: $O (V^3)$, where $V$ is the number of vertices

Algorithm Workflow

The algorithm uses a dynamic programming approach to iteratively improve the estimate of the shortest path between all pairs of vertices. It operates on a matrix where the value at the $i^{th}$ row and $j^{th}$ column represents the shortest path from vertex $i$ to vertex $j$. Initially, this matrix is filled with the direct distances between vertices, which is the weight of the edge connecting them, or infinity if no direct edge exists.

The core of the algorithm involves three nested loops, each running through all vertices. For each pair of vertices $i$ and $j$, the algorithm considers whether a vertex $k$ can act as an intermediate point on a shorter path between $i$ and $j$ than any previously known paths. The decision is based on the equation:

$$d[i, j] = \min(d[i, j], d[i, k] + d[k, j])$$

This step is repeated for each vertex $k$, effectively testing every vertex as an intermediate point in paths between all pairs of vertices.

1. Initialize:

   • Create a 2D array dist to store the shortest path distances.
   • Set dist[i][j] to the weight of the edge between vertex i and vertex j if such an edge exists. Otherwise, set it to infinity (or a very large value).
   • Set dist[i][i] = 0 for all i (self-loops have zero cost).

2. Iterate:

   • Use each vertex k as an intermediate vertex and update the distances for all pairs (i, j):
   • If dist[i][j] > dist[i][k] + dist[k][j], update dist[i][j] to dist[i][k] + dist[k][j].

3. Detect Negative Cycles:

   • After the above steps, if any diagonal value dist[i][i] is negative, then the graph contains a negative weight cycle.

Complexity

Time Complexity

The time complexity of the Floyd-Warshall algorithm is $O(|V|^3)$, where $|V|$ is the number of vertices in the graph. This complexity arises because the algorithm requires three nested loops over the vertices. Despite this seemingly high complexity, the algorithm is efficient in practice for dense graphs due to its straightforward implementation and the constant time required for each update operation.

Space Complexity

The space complexity of the Floyd-Warshall algorithm is $O(|V|^2)$ because it maintains a $|V| \times |V|$ matrix that stores the shortest path distances between all pairs of vertices.

Pseudocode

The algorithm initializes a matrix $D$ of distances with $D[i][j]$ being the weight of the edge $(i, j)$ or $\infty$ if there is no direct edge between the vertices. If $i = j$, $D[i][j] = 0$. The core of the algorithm then updates the matrix $D$ to include the shortest possible paths between each pair of nodes through an intermediate vertex.

function FloydWarshall(W, n) 
    D := W     // Start with the weight matrix
    for k from 1 to n
        for i from 1 to n
            for j from 1 to n
                if D[i][k] + D[k][j] < D[i][j]
                    D[i][j] = D[i][k] + D[k][j]
    return D

Parameters:

• $W$: The initial matrix of edge weights between vertices.
• $n$: The number of vertices in the graph.

Example in Python

Here’s a practical implementation of the Floyd-Warshall algorithm in Python:

def floyd_warshall(weights, num_vertices):
    # Create a distance matrix from weight matrix
    dist = list(map(lambda i: list(map(lambda j: j, i)), weights))
    
    # Apply Floyd-Warshall Algorithm
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                # Update the distance matrix with the shorter path found
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

# Example graph represented as an adjacency matrix
inf = float('inf')
graph = [
    [0, 3, inf, inf],
    [2, 0, inf, inf],
    [inf, 7, 0, 1],
    [6, inf, inf, 0]
]

# Running the algorithm
shortest_paths = floyd_warshall(graph, 4)
for row in shortest_paths:
    print(row)

This example utilizes a matrix where each row and column represent a vertex in the graph, and the values represent the weights of the edges or $\infty$ if no direct edge exists. The output will display the shortest paths between all pairs of vertices.

Applications

• All Pairs Shortest Path Problem: Finds the shortest path between every pair of nodes in a graph, useful for network routing.
• Transitive Closure of a Graph: Can be used to determine the reachability of one node from another in $O (V^3)$ time.
• Testing Graphs for Negative Weight Cycles: The presence of values on the diagonal of the distance matrix $D[i][i]$ that are negative indicates a negative weight cycle.